Thread: [Xcode-Mac OS X] evaluate prefix expression using queues

this is the question:

One way to evaluate a prefix expression is to use a queue. To evaluate the expression, scan it repeatedly until the final expression value is known. In
each scan, read the tokens and store them in a queue. In each scan, replace an operator followed by two operands by the calculated values.
For example, the following expression is a prefix expression, which is evaluated to 159.
-+*9+28*+4863
We scan the expression and score it in a queue. During the scan, when an operator is followed by two operands, such as + 2 8, we put the result, 10 in the queue.
After the first scan, we have - + * 9 10 * 12 6 3
After the second scan, we have - + 90 72 3
After the third scan, we have - 162 3
After the fourth scan, we have 159




HERE IS THE APPROACH I TRIED:

1 .first take the char in expr[]="-+*9+28*+4863 ", calculate and put it in a queue .
2. again put t items in the queue to the expr[]= "-+*910*1263".
3. and repeat 1 and 2 till q->count is 1.



HERE IS THE CODE SO FAR I TRIED:

Code:

#include <stdio.h>
#include <stdlib.h>
#include<ctype.h>
#include<math.h>



typedef struct node
{
    char data[8];
    struct node *link;
} NODE;

typedef struct queue
{
    NODE *front;
    NODE *rear;
    int count;
} QUEUE;

QUEUE* CreateQueue()
{
    QUEUE* q = (QUEUE*)malloc(sizeof(QUEUE));
    q->front = NULL;
    q->rear = NULL;
    q->count = 0;
    return q;
}

void Enqueue(QUEUE *q, char *dataIn)
{
    NODE *newNode = (NODE*)malloc(sizeof(NODE));
    strcpy(newNode->data,dataIn);
    newNode->link = NULL;
    if (q->front == NULL)
        q->front = newNode;
    else
        q->rear->link = newNode;
    q->rear = newNode;
    q->count++;
}

char* Dequeue(QUEUE *q)
{
    char *dataout;
    NODE *temp = q->front;
    dataout = q->front->data;
    if (q->count == 1)
        q->rear = NULL;
    q->front = q->front->link;
    q->count--;
    free(temp);
    return dataout;
}

int QueueFront(QUEUE *q, char *dataOut)
{
    if (q->count == 0)
        return 0;
    dataOut = q->front->data;
    return 1;
}

int EmptyQueue(QUEUE *q)
{
    if (q->count == 0)
        return 1;
    else
        return 0;
}

int FullQueue(QUEUE *q)
{
    NODE *temp = (NODE*)malloc(sizeof(NODE));
    if (temp == NULL)
        return 1;
    else
    {
        free(temp);
        return 0;
    }
}

int QueueCount(QUEUE *q)
{
    return q->count;
}

void DestroyQueue(QUEUE *q)
{
    NODE *temp;
    while (q->front != NULL)
    {
        temp = q->front;
        q->front = q->front->link;
        free(temp);
    }
    free(q);
}

int calculate(char a, int b, int c)
{
    
    if(a=='+')
        return (b+c);
    
    else if(a=='-')
        return (b-c);
    else if(a=='*')
        return (b*c);
    else if(a=='/')
        return (b/c);
}

int main()
{
    char expr[]="-+9+28*+4863";
    printf("%s",expr);
    QUEUE *q = CreateQueue();
    char data1[8],data2[8],data[8],data3[8],data4[8];
    int i=0,j=1,k=2,l=0;
    int a,b,r;
    char *p,*datain,*dataOut;
    p=data3;dataOut=data4;
    while((QueueCount(q)>1))
    {
        i=0;j=1;k=3;l=0;
        
    while((expr[i]!='\0'))
    {
        if(ispunct(expr[i])&&isdigit(expr[j])&&isdigit(expr[k]))
        
           {
               data1[0]=expr[j];data1[1]='\0';
               data2[0]=expr[k];data2[1]='\0';
               
               a=atoi(data1);b=atoi(data2);
               r=calculate(expr[i],a,b);
               //itoa (r, data, 10);
               sprintf(data,"%d",r);
               datain=data;
               Enqueue(q, datain);
               i=i+3;j=j+3;k=k+3;
           }
        else
        {
            data[0]=expr[i];data[1]='\0';
            datain=data;
            Enqueue(q,datain);
            i++;j++;k++;
        }
    } 
    
    
    while(EmptyQueue(q))
    {
       dataOut=Dequeue(q);
        expr[l]=*dataOut;
        l++;
    }
            expr[l]='\0';

    }

    return 0;
}

i am facing problem in the last while loop.
here i don't know how to convert string to char again and put in the expr[].

now i feel that my approach is wrong, could somebody help me ..

@manichandra i think you can write a function like str_char(char *s) that collects and string and starts to read each character at a time and store in an array and then return the number of characters stored and stops reading at a '\0' character. that'll help.

Originally Posted by Salem

[Xcode-Mac OS X] evaluate prefix expression using queues - Dev Shed

thanks. i did it with different approach.

Code:

#include <stdio.h>
#include <stdlib.h>
#include<ctype.h>
#include <string.h>
typedef struct node
{
    char data[16];
    struct node *link;
} NODE;
typedef struct queue
{
    NODE *front;
    NODE *rear;
    int count;
} QUEUE;
QUEUE* CreateQueue()
{
    QUEUE* q = (QUEUE*)malloc(sizeof(QUEUE));  
    q->front = NULL;                           
    q->rear = NULL;                            
    q->count = 0;                              
    return q;
}
void Enqueue(QUEUE *q, char* dataIn)
{
    NODE *newNode = (NODE*)malloc(sizeof(NODE));   
    strcpy(newNode->data, dataIn);                 
    newNode->link = NULL;
    if (q->front == NULL)
        q->front = newNode;                        
    else
        q->rear->link = newNode;
    q->rear = newNode;
    //printf(" New node is %s", dataIn);
    q->count++;                            
}
void Dequeue(QUEUE *q, char *dataOut)
{
    NODE *temp = q->front;
    strcpy(dataOut, q->front->data);    
    if (q->count == 1)                  
        q->rear = NULL;                 
    q->front = q->front->link;          
    q->count--;                         
    free(temp);
}
int QueueCount(QUEUE *q)
{
    return q->count;         
}
void Display(QUEUE *q)
{
    NODE *pLoc = q->front; // first node
    printf("\n");
    printf("expression: ");
    while (pLoc != NULL)
    {
        printf("%s ", pLoc->data);
        pLoc = pLoc->link;
    }    
}
void DestroyQueue(QUEUE *q)
{
    NODE *temp;
    while (q->front != NULL)
    {
        temp = q->front;
        q->front = q->front->link;
        free(temp);
    }
    free(q);
}
int calculate(char a, int b, int c)
{
    
    if(a=='+')
        return (b+c);
    
    else if(a=='-')
        return (b-c);
    else if(a=='*')
        return (b*c);
    else if(a=='/')
        return (b/c);
    else
        return -1;
}
void stringcopy(char data1[],char* dataptr)
{
    int i=0;
    while(*dataptr!='\0')
    {
        data1[i]=*dataptr;
        dataptr++;
        i++;
    }
    data1[i]='\0';
}
int calculateExpression(QUEUE *q)
{
    char data[16], data1[16],data2[16],temp_opr, temp_op1, temp_op2, *dataptr;
    int i, operand1, operand2, value;
    while ((QueueCount(q)!=1))    { 
        Dequeue(q, data);
        temp_opr=data[0];
   if(ispunct(temp_opr))// if temp_opr is punctuation '+' or '_' or '*' or '/'
   {
    dataptr=q->front->data;//data pointer is pointing to the 2nd data in the queue
    temp_op1=*dataptr;
    stringcopy(data1,dataptr); // copies the string pointed by dataptr to data1
            
    dataptr=q->front->link->data;
    temp_op2=*dataptr;      //data pointer is poiting to the 3rd data in the queue
    stringcopy(data2,dataptr); // copies the string pointed by dataptr to data2
     if(!ispunct(temp_op1)&&!ispunct(temp_op2))
            {
                
                operand1= atoi (data1);      
                operand2= atoi (data2);       
                Dequeue(q, data1);   
                Dequeue(q, data2);   
                value=calculate(temp_opr,operand1, operand2);
                printf (" \n\nafter calculating %d %c %d = %d\n",operand1,temp_opr,operand2,value);
                // itoa (value, data, 10);      
                sprintf(data,"%d",value);
                dataptr=data;
                   Enqueue(q, dataptr);  
                Display(q);
            }
            else
            {
                dataptr=data;                   
                Enqueue(q, dataptr);   
                Display(q);
            }
        }
        else
        {
            dataptr=data;
            Enqueue(q, dataptr); 
            Display(q);
        }     
    }
    Dequeue(q, data);  
    return atoi(data); 
int main()
{
    char expr[128] = "- + * 9 + 2 8 * + 4 8 6 3";
    char *token;
    int finalvalue;
    QUEUE *q = CreateQueue();   
    token = expr;
    while ((token = strtok(token, " ")))
    {
        Enqueue(q, token);
        token = NULL;
    }
    finalvalue=calculateExpression(q);
    printf("\n\n value of the expression %d", finalvalue);    
    DestroyQueue(q);  
}

OUTPUT

expression: - + * 9 + 2 8 * + 4 8 6 3
expression: + * 9 + 2 8 * + 4 8 6 3 -
expression: * 9 + 2 8 * + 4 8 6 3 - +
expression: 9 + 2 8 * + 4 8 6 3 - + *
expression: + 2 8 * + 4 8 6 3 - + * 9

after calculating 2 + 8 = 10

expression: * + 4 8 6 3 - + * 9 10
expression: + 4 8 6 3 - + * 9 10 *

after calculating 4 + 8 = 12

expression: 6 3 - + * 9 10 * 12
expression: 3 - + * 9 10 * 12 6
expression: - + * 9 10 * 12 6 3
expression: + * 9 10 * 12 6 3 -
expression: * 9 10 * 12 6 3 - +

after calculating 9 * 10 = 90

expression: * 12 6 3 - + 90

after calculating 12 * 6 = 72

expression: 3 - + 90 72
expression: - + 90 72 3
expression: + 90 72 3 -

after calculating 90 + 72 = 162

expression: 3 - 162
expression: - 162 3

after calculating 162 - 3 = 159

expression: 159

final value of the expression 159